Open in Colab >

BurritoOptimizationGame.com Game Guide | Teaching Guide Notebook by Alison Cozad | Game credits

The Burrito Optimization Game is an educational game designed to introduce students to the power of optimization. In the game, the player places burrito trucks on a city map to earn as much profit as possible. In playing the game, the player is essentially solving an optimization problem “by hand”. The game is designed to introduce players to optimization—what it is, what it’s useful for, and why it’s hard to do by hand. To play the game, you must be logged in to your Gurobi account on a desktop.

In this notebook, we will learn how to write the Burrito game optimization model for any day in Round 1 using the data downloaded from the game.

This modeling tutorial is at the introductory level, where we assume that you know Python and have a background in a discipline that uses quantitative methods.

Here are a few handy resources to have ready:

• Gurobi Python Documentation
• Gurobi Python Examples
• Burrito Optimization Game: Teaching Guide
• Burrito Optimization Game: Game Guide

---

Problem description

Guroble has just set up business in Burritoville! Guroble needs your assistance planning where to place its burrito trucks to serve hungry customers throughout the city and maximize its profit. Truck placement must be carefully planned because every truck has a cost, but its ability to earn revenue depends on how close it is to potential customers.

Your task in the game:

Your task in this notebook:

Write a model to select the optimal burrito truck placement to maximize profits. You will be solving for one day in Round 1.

---

Before you dive into this model,

If you haven't already, we recommend playing Days 1 and 2 in Round 1 of the BurritoOptimizationGame.com to learn about Burritoville and the problem we are trying to solve. Then, ask yourself:

• What seems easy or hard about locating burrito trucks?
• Did you find a solution that was close to optimal?
• Should you order a burrito now or wait until you are done with this notebook?
• What strategy did you use? I bet you wish you had your own optimization model, eh? (Cue shameless promotion of this Jupyter Notebook).

Let's get started

Throughout the rest of this notebook, we will

1. Define the data structures
2. Create the Gurobi model object
3. Add decision variables
4. Add constraints
5. Set the objective function
6. Solve the model
7. Retrieve solution values

0. The obligatory part

I know this wasn't on the list that I just gave you. Alas, this is the obligatory part of all python code: installing and importing packages.

First, let's install a few packages as needed

!pip install gurobipy
!pip install plotly
!pip install requests

Next, we will import the Gurobi callable library and import the GRB class into the main namespace.

import gurobipy as gp
from gurobipy import GRB

× Quick Tip

The two import lines above will be needed each time you want to use gurobipy. You are encouraged to completely forget this part and copy-and-paste it for each new Gurobi model you write ;).

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

1. Define the data structures

The Burrito Optimization Game lets you download the data to define the model. To ensure we have time for the fun stuff, we have added this below for you.

Here is the data overlayed on the map:

What do we know about Burritoville on a given day?

• Scalar data: burrito_price, ingredient_cost, and truck_cost
• Truck data: Set of trucks spots that are available truck_spots[t]
• Buildings that have customer demand: Total demand demand[b] and scaled demand by a factor of how far the customer will have to walk scaled_demand[b,t]

Other data such as map coordinates and building names are used for plotting only. In the cells below, we will recreate the BurritoOptimizationGame model using data from CSV files that are downloadable from the game.

To start, pick the round and day that you would like to solve for

# Round and day specific string. Note: This model is only valid for Round 1
path = "https://raw.githubusercontent.com/Gurobi/modeling-examples/master/burrito_optimization_game/data/"

### CHANGE THIS TO SWITCH DAYS. ###
# This should match the csv filenames (e.g., round1-day1, round1-day2, round1-day3...)
round_day_str = "round1-day1" 
#round_day_str = "round1-day2" 
#round_day_str = "round1-day3" 
#round_day_str = "round1-day4" 

Read in and define data structures

We will define the following from these data structures:

• From the 'Problem Data' we will get basic data that will be stored as scalars: burrito_price, ingredient_cost, and truck_cost
• From 'Truck node data' we are given the possible truck locations and their coordinates on the map. We will not use the coordinates in the model, but we will use them for plotting. From this, we create the truck_spots set and the truck_coordinates dictionary.
• From 'Demand node data' we get a list of buildings with customer demand by building. We are also given the coordinates and building names --- which we find pretty clever. We use the Gurobi Python multidict() function to initialize one or more dictionaries with a single statement. The function takes a dictionary as its argument. The keys represent the possible combinations of buildings and truck spots.
• From 'Demand-Truck data' we get information about how the demand scales with each building location and truck spot pair. Customers are only willing to walk so far to a burrito truck, and the actual number of customers you win from a building is smaller the farther away the truck is from the building. If the nearest truck is too far away, you won’t win any customers from that building. To account for this, there is a demand multiplier based on how far a customer can walk from their building to a truck spot. The scaled demand below is the product of the demand multiplier and the total customer demand at a building. We will also extract this data using the Gurobi Python multidict() function. From this, we get the scaled_demand[b,t] values.

These data structures are created in the following cell.

import pandas as pd

# Define the urls to pull data from
urls={
    'Problem data': path + round_day_str + "_problem_data.csv",
    'Truck node data': path + round_day_str + "_truck_node_data.csv",
    'Demand node data': path + round_day_str + "_demand_node_data.csv",
    'Demand-Truck data': path + round_day_str + "_demand_truck_data.csv" , 
}

print(f"Here is a summary of '{round_day_str}':")

# Read in basic problem data
url = urls['Problem data']
df = pd.read_csv(url)
burrito_price = float(df['burrito_price'][0])
ingredient_cost = float(df['ingredient_cost'][0])
truck_cost = float(df['truck_cost'][0])
print(f"  - The burritos cost ₲{ingredient_cost} to make and are sold for ₲{burrito_price}. Each truck costs ₲{truck_cost} to use per day.")

# Read in truck node data
url = urls['Truck node data']
df = pd.read_csv(url)
truck_coordinates = {row['index']:(float(row['x']),float(row['y'])) for ind,row in df.iterrows()}
truck_spots = truck_coordinates.keys()
print(f"  - There are {len(truck_spots)} available 'truck_spots' or places where a truck can be placed around Burritoville.")
 
# Read in building data
url = urls['Demand node data']
df = pd.read_csv(url)
buildings, building_names, building_coordinates, demand = gp.multidict({
        row['index']: [row['name'], (float(row['x']), float(row['y'])), float(row['demand'])] for ind,row in df.iterrows()
    })
print(f"  - There are in {len(buildings)} buildings with hungry customers also known as demand nodes.")


# Read in paired building and truck data
url = urls['Demand-Truck data']
df = pd.read_csv(url)
building_truck_spot_pairs, distance, scaled_demand = gp.multidict({
        (row['demand_node_index'], row['truck_node_index']): [float(row['distance']), float(row['scaled_demand'])] for ind,row in df.iterrows() if float(row['scaled_demand'])>0# (building, truck_spot): distance, scaled_demand
    })
print(f"  - There are in {len(building_truck_spot_pairs)} pairs of trucks spots and buildings with hungry customers.")

Here is a summary of 'round1-day1':
  - The burritos cost ₲5.0 to make and are sold for ₲10.0. Each truck costs ₲250.0 to use per day.
  - There are 16 available 'truck_spots' or places where a truck can be placed around Burritoville.
  - There are in 15 buildings with hungry customers also known as demand nodes.
  - There are in 113 pairs of trucks spots and buildings with hungry customers.

Current map layout with this data

We can now view this data on our Burritoville map to make sure everything looks correct.

# Plot the truck spots and customer demands on the Burritoville map
import requests
r = requests.get('https://raw.githubusercontent.com/Gurobi/modeling-examples/master/burrito_optimization_game/util/show_map.py')
with open('show_map_local.py', 'w') as f:
    f.write(r.text)
from show_map_local import show_map

show_map(buildings, building_names, building_coordinates, demand, truck_coordinates)

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

2. Begin building the model

In the next four steps, we will be creating the following model:

$$ \begin{align*} {\rm maximize} & \quad \displaystyle \sum_{b\in \mathcal{B}} \ \displaystyle \sum_{t\in \mathcal{T}} \ ( r - k) \alpha_{bt} d_b y_{bt} - \displaystyle \sum_{t\in \mathcal{T}} f_t x_t \\ \\ {\rm s.t.} & \quad y_{bt} \leq x_t & \quad \forall b\in {\mathcal{B}} ,t\in {\mathcal{T}} \\ & \quad \displaystyle \sum_{t\in \mathcal{T}} y_{bt} \leq 1 & \quad \forall b\in {\mathcal{B}} \\ & \quad x_t, y_{bt} \in \{0,1\} & \quad \forall b\in {\mathcal{B}} ,t\in {\mathcal{T}} \\ \\ \end{align*} $$

where we have two sets (created above):

$$ \begin{align*} \mathcal{T} & \quad \text{is the set of available truck spots } \ t & \quad \texttt{truck}\_ \texttt{spots} \\ \mathcal{B} & \quad \text{is the set of buildings with customer demand } \ b & \quad \texttt{buildings} \\ \\ \end{align*} $$

and the following decision variables:

$$ \begin{align*} x_t & \quad \text{is 1 if a truck is placed at truck spot } t\in \mathcal{T} \text{; 0 otherwise.} & \quad \texttt{x}\_ \texttt{placed[t]} \\ y_{bt} & \quad \text{is 1 if truck } t\in\mathcal{T} \text{ serves burritos to customers from building } b\in \mathcal{B} \text{; 0 otherwise.} & \quad \texttt{y}\_ \texttt{served[b,t]} \\ \\ \end{align*} $$

and the following scalars and data structures (created above):

$$ \begin{align*} r & \quad \text{is the revenue from each burrito in ₲ per burrito.} & \quad \texttt{burrito}\_ \texttt{price} \\ k & \quad \text{is the ingredient cost for each burrito in ₲ per burrito} & \quad \texttt{ingredient}\_ \texttt{cost} \\ \alpha_{bt},d_b & \quad \text{are the demand multiplier and demand. These have been combined into one scaled demand.} & \quad \texttt{scaled}\_ \texttt{demand[b,t]} \\ f_t & \quad \text{ is the cost to place a truck for the day} & \quad \texttt{truck}\_ \texttt{cost}\\ \end{align*} $$

If you have already peeked at the notation in the Game Guide, you may notice that the $i$ and $j$ indices have disappeared. We have changed them to $t$ for each truck spot and $b$ for each building with demand. But it's the same idea.

To start, we will need to create the model() object in Gurobi. The Model object holds a single optimization problem. It consists of a set of variables, a set of constraints, and an objective function.

# Declare and initialize model
model = gp.Model("Burrito Optimization Game")

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

3. Add Decision variables

To solve the Burrito Optimization Game problem, we need to identify where we will place our trucks. Each truck can only be placed in an available truck spot. We also need to know which buildings will be served by which truck. Here are the two variables we are creating:

• x_placed[t] is 1 if we place a truck at truck spot t, otherwise x_placed[t] is 0
• y_served[b,t] is 1 if building b is served by a truck placed at truck spot t, otherwise y_served[b,t] is 0

Here we are creating variables using addVars() function for x_placed and y_served.

# Create decision variables for the Burrito Optimization Game model
x_placed = model.addVars(truck_spots, vtype=GRB.BINARY, name="x_placed")
y_served = model.addVars(building_truck_spot_pairs, vtype=GRB.BINARY, name="y_served")

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

4. Add Constraints

We will begin adding the constraints that define our problem.

Truck must be open at a truck_spot to serve the customer

Here we must ensure that a truck exists in a truck spot if a customer is served there. No truck, no burrito : (.

In the next cell, we will create these constraints in one call to addConstrs() to add to the model

$$ \begin{align*} y_{bt} \leq x_t & \quad \quad \forall b\in {\mathcal{B}} ,t\in {\mathcal{T}} \\ \end{align*} $$

# Create truck-must-exist constraints
cons1 = model.addConstrs((y_served[b,t] <= x_placed[t] 
                          for b,t in building_truck_spot_pairs), 
                          name = "Ensure_truck_spot_open_to_serve")

× Quick Tip

There is more than one way to create these constraints. You can add the constraints one-at-a-time using addConstr() or with one line using addConstrs(). We have used the latter when creating these constraints because it is more efficient and compact.

Only one truck per customer at a given building

The customers from one building will all be served by up to one truck. $$ \begin{align*} \displaystyle \sum_{t\in \mathcal{T}} y_{bt} \leq 1 & \quad \quad \forall b\in {\mathcal{B}} \\ \end{align*} $$

Here we are using the y_served.sum() function to make it easy to do a summation over a variable.

# Create only one truck per customers at building constraint
cons2 = model.addConstrs((y_served.sum(b,'*') <= 1 for b in buildings), 
                         name="Ensure_one_truck_per_customers_at_building")

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

5. Set the objective

The objective is to maximize the total profit.

To set the objective, we will first define the revenue using a nested summation. This can be accomplished using the function. For convenience and readability, we will split the objective into the burrito revenue and truck costs:

$$ \begin{align*} {\rm maximize} & \quad \displaystyle \sum_{b\in \mathcal{B}} \ \displaystyle \sum_{t\in \mathcal{T}} \ ( r - k) \alpha_{bt} d_b y_{bt} - \displaystyle \sum_{t\in \mathcal{T}} f_t x_t \\ \\ \end{align*} $$

Here, we are only creating new linear expressions, not new variables. Then we will use the setObjective() method to set the objective.

# Objective: maximize total profit = burrito_revenue - total_truck_cost
burrito_revenue = (burrito_price - ingredient_cost)*y_served.prod(scaled_demand) # This is the nested summation
total_truck_cost = truck_cost*x_placed.sum('*')

model.setObjective(burrito_revenue - total_truck_cost, GRB.MAXIMIZE)

Celebrate and check your work

model.write('burrito_game.lp')

× Quick Tip

In the cell above, we wrote out the model as an LP file. This is a human-readable format that can allow you to check to make sure your constraints and objectives look right. This has been saved to this local directory.

Take a look at burrito_game.lp. Does everything look correct? If so, please consider celebrating. Eat a burrito. Do an optimal dance.

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

6. Solve the model

We use the optimize() method of the Gurobi/Python API to solve the problem we have defined for the model object model.

model.optimize()

Gurobi Optimizer version 9.5.0 build v9.5.0rc5 (mac64[x86])
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads
Optimize a model with 128 rows, 129 columns and 339 nonzeros
Model fingerprint: 0x42dc3551
Variable types: 0 continuous, 129 integer (129 binary)
Coefficient statistics:
  Matrix range     [1e+00, 1e+00]
  Objective range  [5e+00, 2e+02]
  Bounds range     [1e+00, 1e+00]
  RHS range        [1e+00, 1e+00]
Found heuristic solution: objective -0.0000000
Presolve removed 17 rows and 20 columns
Presolve time: 0.00s
Presolved: 111 rows, 109 columns, 288 nonzeros
Variable types: 0 continuous, 109 integer (109 binary)

Root relaxation: objective 6.000000e+02, 35 iterations, 0.00 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

*    0     0               0     600.0000000  600.00000  0.00%     -    0s

Explored 1 nodes (35 simplex iterations) in 0.03 seconds (0.00 work units)
Thread count was 8 (of 8 available processors)

Solution count 2: 600 -0 

Optimal solution found (tolerance 1.00e-04)
Best objective 6.000000000000e+02, best bound 6.000000000000e+02, gap 0.0000%

Before we start digging into the solution, let's check the solution. If the model is not optimal, check the Optimization Status Codes page.

status = model.status
if status == GRB.OPTIMAL:
    print(f"The final objective is ")
    print(f"     Burrito revenue        ₲{burrito_revenue.getValue()}")
    print(f" -  Total truck cost     -  ₲{total_truck_cost.getValue()}")
    print(f"-----------------------------------")
    print(f"              Profit        ₲{model.objVal}")
else:
    print(f"Model is not optimal, status = {status}")

The final objective is 
     Burrito revenue        ₲1100.0
 -  Total truck cost     -  ₲500.0
-----------------------------------
              Profit        ₲600.0

Jump to Top | Data | Model | Variables | Constraints | Objective | Optimize! | View the solution

---

7. View the solution

# Plot the solution on the Burritoville Map
placed_trucks = [t for t in x_placed if x_placed[t].X ==1]
show_map(buildings, building_names, building_coordinates, demand, truck_coordinates, placed_trucks = placed_trucks)

Before you exit, free up Gurobi resources

After you are done, it is a best practice to free up any Gurobi resources associated with the model object and environment. This will release any shared licenses and end the job on the cloud or compute server.

To do this, call Model.dispose() on all Model objects, Env.dispose() on any Env objects you created, or disposeDefaultEnv() if you used the default environment instead.

# Free Gurobi resources: Model and environment
model.dispose()
gp.disposeDefaultEnv()

Freeing default Gurobi environment